package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

import java.util.LinkedList;

public class _226_invert_tree {
    
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode left = invertTree(root.left);
        root.left = invertTree(root.right);
        root.right = left;
        return root;
    }
    
    /**
     * 这个迭代可以写写，没那么傻逼
     *
     * 原理是翻转每一个遇到的节点
     *
     * */
    public TreeNode invertTree2(TreeNode root) {
        if (root == null) return null;
        TreeNode res = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            TreeNode t = node.left;
            node.left = node.right;
            node.right = t;
            
            root = node.left;
        }
        return res;
    }
}
